class Solution {
public:
    const int INF=0x3f3f3f3f;

    vector<int> Dijkstra(vector<vector<pair<int, int>>> &graph, int n, int u)
    {
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q; //<dist, v>
        vector<int> dist(n+1, INF);
        dist[u]=0;
        q.push({0, u});
        while(!q.empty())
        {
            auto [disttemp, temp]=q.top(); q.pop(); //(dist[u][temp], 中间节点) //u->temp->v < u->v
            if(disttemp>dist[temp]) continue; //当前边节点不是最优

            for(auto &[v, distv]:graph[temp]) //(v, dist[temp][v])
            {
                // if(v==0) continue; //是否有0点
                int Newdist=disttemp+distv;
                if(Newdist<dist[v]) //中间节点可以更新这个最短路径
                {
                    dist[v]=Newdist;
                    q.push({Newdist, v});
                }
            }
        }
        return dist;
    }

    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<pair<int, int>>> graph(n+1);
        for(auto &e:times)
            graph[e[0]].push_back({e[1], e[2]});
        vector<int> dist=Dijkstra(graph, n, k);

        int ans=0;
        for(int i=1; i<=n; i++) ans=max(ans, dist[i]);
        //int ans=ranges::max(dist); //是否考虑0点
        return ans==INF?-1:ans;
    }
};